package 数据结构;

public class LeetCode75_颜色分类 {
    public void sortColors(int[] nums) {
        if(nums == null || nums.length == 1) {
            return;
        }
        int left = 0;
        int right = nums.length-1;
        patition(nums, left, right);
    }
    // 双路快排
    public void patition(int[] nums, int left, int right) {
        int white = 1;
        int red = left;
        int blue = right + 1;

        while(left < blue) {
            if(nums[left] < white) {
                swap(nums, red, left);
                red++;
                left++;
            }else if(nums[left] > white) {
                swap(nums, blue-1,left);
                blue--;
            }else {
                left++;
            }
        }
    }
    public void swap(int[] nums, int swap1, int swap2) {
        int temp = nums[swap1];
        nums[swap1] = nums[swap2];
        nums[swap2] = temp;
    }
}
